|
In mathematics, a transitive reduction of a directed graph is a graph with as few edges as possible that has the same reachability relation as the given graph. Equivalently, the given graph and its transitive reduction should have the same transitive closure as each other, and its transitive reduction should have as few edges as possible among all graphs with this property. Transitive reductions were introduced by , who provided tight bounds on the computational complexity of constructing them. If a given graph is a finite directed acyclic graph, its transitive reduction is unique, and is a subgraph of the given graph. However, uniqueness is not guaranteed for graphs with cycles, and for infinite graphs not even existence is guaranteed. The closely related concept of a minimum equivalent graph is a subgraph of the given graph that has the same reachability relation and as few edges as possible. For finite directed acyclic graphs, the minimum equivalent graph is the same as the transitive reduction. However, for graphs that may contain cycles, minimum equivalent graphs are NP-hard to construct, while transitive reductions can still be constructed in polynomial time. Transitive reductions can also be defined for more abstract binary relations on sets, by interpreting the pairs of the relation as arcs in a graph. ==In directed acyclic graphs== The transitive reduction of a finite directed graph ''G'' is a graph with the fewest possible edges that has the same reachability relation as the original graph. That is, if there is a path from a vertex ''x'' to a vertex ''y'' in graph ''G'', there must also be a path from ''x'' to ''y'' in the transitive reduction of ''G'', and vice versa. The following image displays drawings of graphs corresponding to a non-transitive binary relation (on the left) and its transitive reduction (on the right). The transitive reduction of a finite directed acyclic graph ''G'' is unique, and consists of the edges of ''G'' that form the only path between their endpoints. In particular, it is always a subgraph of the given graph. For this reason, the transitive reduction coincides with the minimum equivalent graph in this case. In the mathematical theory of binary relations, any relation ''R'' on a set ''X'' may be thought of as a directed graph that has the set ''X'' as its vertex set and that has an arc ''xy'' for every ordered pair of elements that are related in ''R''. In particular, this method lets partially ordered sets be reinterpreted as directed acyclic graphs, in which there is an arc ''xy'' in the graph whenever there is an order relation ''x'' < ''y'' between the given pair of elements of the partial order. When the transitive reduction operation is applied to a directed acyclic graph that has been constructed in this way, it generates the covering relation of the partial order, which is frequently given visual expression by means of a Hasse diagram. Transitive reduction has been used on networks which can be represented as directed acyclic graphs (e.g. citation networks) to reveal structural differences between networks.〔http://arxiv.org/abs/1310.8224〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「transitive reduction」の詳細全文を読む スポンサード リンク
|